package com.shuang.dp11;
//
//class Solution {
//    //转为背包问题
//    //假设将集合分成两个子集 一个是加法的集合 一个是减法的集合 加法集合的总和为x，那么减法集合对应的总和就是sum - x。
//    // 所以我们要求的是 x - (sum - x) = target
//    // x = (target + sum) / 2 而当不能整除时 则说明找不到这样的加法和减法集合得到目标值 直接返回0
//    //所以转化为背包问题为 装满容量为x的背包 一共有多少种方法
//    //方法一：
//    //使用二维dp数组
//    public int findTargetSumWays(int[] nums, int target) {
//        //数组总和
//        int sum = 0;
//        for (int num : nums){
//            sum += num;
//        }
//
//        //目标值的绝对值大于数组总和了 则不可能有方法成立
//        if (Math.abs(target) > sum){
//            return 0;
//        }
//
//        //x = (target + sum) / 2 不能整除时也没有方法成立\
//        if ((target + sum) % 2 != 0){
//            return 0;
//        }
//
//        //背包容量
//        int n = (target + sum) / 2;
//        //二维dp数组 dp[i][j] 表示从[0,i]选取物品即数字nums[i]（nums[i]代表重量） 装满容量为j的背包 一共有dp[i][j]种方法
//        int[][] dp = new int[nums.length][n + 1];
//
//        //递归公式
//        //dp[i][j] 当前位置放与不放i物品 两种状态 不放i物品装满j容量的背包方法有 dp[i - 1][j]种
//        //放i的情况：先是容量够放i才可以 然后先把物品i的容量减去 在前i-1个物品中装满有 dp[i - 1][j - nums[i]]种方法 在加一个物品i正好装满 所以放i情况下装满容量j的方法有 dp[i - 1][j - nums[i]]种
//
//        //初始化dp数组
//        //第一行 物品0 往容量为0-n的背包里装 只有当容量恰好等于物品0的重量时才可以装满也就是此时有1种方法 其余不是装不满就是装不下 所以都是0种方法
//        //第一列 容量为0的背包里装物品 不装物品是一种方法 但是如果有物品是重量0的情况 假设有m个物品重量为0 每个物品都可以选择放与不放 所以 第一列方法应该有 2的m次方 这么多种方法
//
//        //初始化第一行
//        // for (int i = 0; i <= n; i++){
//        //     if (i == nums[0]){
//        //         dp[0][i] = 1;
//        //         break;
//        //     }
//        // }
//        //防止索引越界
//        if (n >= nums[0]){
//            dp[0][nums[0]] = 1;
//        }
//
//        //初始化第一列
//        //用于记录数组中出现0的次数
//        int zeroNum = 0;
//        for (int i = 0; i < nums.length; i++){
//            if (nums[i] == 0){
//                zeroNum++;
//            }
//            //[0,i]有多少个物品是0 在其中任选i个物品放在容量为0的背包里 一共有的方法如下
//            dp[i][0] = (int)Math.pow(2, zeroNum);
//        }
//
//        //遍历顺序 从左到右 从上到下 如下是先物品 再背包
//        for (int i = 1; i < nums.length; i++){
//            for (int j = 1; j <= n; j++){
//                if (j >= nums[i]){
//                    //当前容量够放物品i 则选择放与不放i的不同种方法加起来是当前位置的方法数
//                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
//                } else {
//                    //当前容量不够放物品i的则只能是
//                    dp[i][j] = dp[i - 1][j];
//                }
//            }
//        }
//
//        return dp[nums.length - 1][n];
//
//    }
//}

class Solution {
    //转为背包问题
    //假设将集合分成两个子集 一个是加法的集合 一个是减法的集合 加法集合的总和为x，那么减法集合对应的总和就是sum - x。
    // 所以我们要求的是 x - (sum - x) = target
    // x = (target + sum) / 2 而当不能整除时 则说明找不到这样的加法和减法集合得到目标值 直接返回0
    //所以转化为背包问题为 装满容量为x的背包 一共有多少种方法
    //方法二：
    //使用一维dp数组：
    public int findTargetSumWays(int[] nums, int target) {
        //数组总和
        int sum = 0;
        for (int num : nums){
            sum += num;
        }

        //目标值的绝对值大于数组总和了 则不可能有方法成立
        if (Math.abs(target) > sum){
            return 0;
        }

        //x = (target + sum) / 2 不能整除时也没有方法成立\
        if ((target + sum) % 2 != 0){
            return 0;
        }

        //背包容量
        int n = (target + sum) / 2;
        //dp数组 dp[j]  装满容量为j的背包 一共有dp[j]种方法
        int[] dp = new int[n + 1];

        //递推公式
        //dp[j] = dp[j] + dp[j - nums[i]]; 即dp[j] += dp[j - nums[i]]


        //初始化dp数组
        dp[0] = 1;//满足程序运行 可以理解为装满容量为0的背包有1种方法


        //遍历顺序 先物品前到后 再背包倒序
        for (int i = 0; i < nums.length; i++){
            for (int j = n; j >= nums[i]; j--){
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[n];

    }
}